giru0116のブログ

リスト構造用関数

#include<stdio.h>
#include<stdlib.h>

typedef struct List {
	int value;
	struct List *next;
}List_t;

/* 以下の関数は引数に指定されたアドレスのリストに対する処理を実行します */

int list_length(List_t *); /* リストに存在する要素の数を戻り値として返します */
void list_clear(List_t *); /* リストの要素を全て削除して初期化します */
void list_display(List_t *); /* リストの要素を先頭から順番に表示します */ 
List_t *insert(List_t *, int, int);
	/* ２番目の引数として挿入する数値を、３番目として挿入する位置を指定します
	 * 不正な数値が指定されていた場合はNULLを返し、それ以外では挿入した要素のアドレスを返します */

int delete(List_t *, int);
	/* ２番目の引数として削除する位置を指定します
	 * 不正な数値が指定されていた場合は-1を返し、それ以外では0を返します */

List_t *insert_first(List_t *, int);
	/* リストの先頭に引数に指定された数値を挿入します。戻り値の仕様は関数insertと同じです */

List_t *insert_last(List_t *, int);
	/* リストの末尾に引数に指定された数値を挿入します。戻り値の仕様は関数insertと同じです */

int delete_first(List_t *);
	/* リストの先頭の数値を削除します。戻り値の仕様は関数deleteと同じです */

int delete_last(List_t *);
	/* リストの末尾の数値を削除します。戻り値の仕様は関数deleteと同じです */

int list_search(List_t *, int);
	/* 引数に指定した数値がリストの何番目にあるかを返します。存在しない場合は-1を返します */

List_t *list_pickup(List_t *, int);
	/* 引数に指定した位置の要素のアドレスを返します。不正な数値であった場合はNULLを返します */

List_t list_reverse(List_t *); /* リストの数値を逆順にしたリストを戻り値として返します */
List_t list_sort(List_t *); /* リストの数値を昇順に並べかえたリストを戻り値として返します */
List_t list_copy(List_t *); /* リストを複製して複製したリストを戻り値として返します */

int list_length(List_t *head)
{
	List_t *p; /* リストの要素を辿るためのループ用変数 */
	int cnt = 0;

	for(p = head->next; p != NULL; p = p->next) {
		++cnt; /* 要素がある度に値を１増やす */
	}

	return cnt;
}

void list_clear(List_t *head)
{
	int r;

	r = delete_first(head);
	/* 最初の要素を削除し、削除できたかどうかを判断するために戻り値を利用 */

	while(r != -1) {
		/* rが-1であった場合全ての要素が削除できたという事になるのでループを終える */
		r = delete_first(head);
	}
	return;
}

void list_display(List_t *head)
{
	List_t *p;

	for(p = head->next; p != NULL; p = p->next) {
		printf("%d\n", p->value);
	}
	return;
}

List_t *insert(List_t *head, int value, int n)
{
	List_t *p, *q;
	int i;
	
	if(n <= 0 || n > (list_length(head) + 1)) {
		/* 0以下、リストの要素数+1よりも上の数値の場合
		そこに要素を挿入する事はできないのでNULLを返して関数を終了 */
			return NULL;
	}
	p = (List_t *)malloc(sizeof(List_t));
	/* List_t型の要素を動的に確保する */

	if(p == NULL) {
		printf("メモリの確保に失敗しました\n");
		exit(1);
	}

	q = head;
	
	for(i = 1; i < n; ++i) {
		/* 引数で指定されたn番目の要素の１つ前まで進める */
		q = q->next;
	}

	p->value = value; /* 確保した変数に値を代入する */
	p->next = q->next;
	q->next = p; /*  */
	
	return p;
}

int delete(List_t *head, int n)
{
	List_t *p, *q;
	int i;

	if(n <= 0 || n > list_length(head)) {
		/* 0以下、リストの要素数より上の場合、削除できないので-1を返して関数を終了 */
		return -1;
	}

	/* headの１つ後とheadのアドレスを格納する */
	p = head->next;
	q = head;
	
	for(i = 1; i < n; ++i) {
		q = p;
		p = p->next;
	}
	q->next = p->next;
	/* １つ前の要素の次の要素として１つ先の要素を指定する
	 * こうしないとリストの連結が上手くいかなくなってしまうため */
	free(p); /* 要素を解放することで削除する */

	return 0;
}

List_t *insert_first(List_t *head, int value)
{
	List_t *p;

	p = (List_t *)malloc(sizeof(List_t));

	if(p == NULL) {
		printf("メモリの確保に失敗しました\n");
		exit(1);
	}
	p->value = value;
	p->next = head->next; /* 確保した要素の次の要素としてそれまでの先頭要素を指定する */
	head->next = p; /* 確保した要素を先頭要素とする */

	return p;
}

List_t *insert_last(List_t *head, int value)
{
	List_t *p;

	/* 関数insertで３つ目の引数として長さ+1を指定する事で最後に要素を挿入 */
	p = insert(head, value, list_length(head) + 1);

	return p;
}

int delete_first(List_t *head)
{
	List_t *p;

	/* リストに要素が無い場合、削除できないので-1を返す */
	if(list_length(head) == 0) {
		return -1;
	}
	
	p = head->next; /* 削除する要素である先頭要素のアドレスをpに代入 */
	head->next = p->next; /* 先頭要素を先頭から２番目の要素とする処理 */
	free(p); /* 先頭要素を解放することで削除する */
	
	return 0;
}

int delete_last(List_t *head)
{
	int r;

	/* 関数deleteで２番目の引数としてリストの長さを指定する事で最後の要素を削除 */
	r = delete(head, list_length(head));

	return r;
}

int list_search(List_t *head, int value)
{
	List_t *p;
	int cnt = 0;

	for(p = head->next; p != NULL; p = p->next) {
		++cnt;
		if(p->value == value) {
			/* valueとリスト内の要素の値が一致した場合、そこが先頭から何番目かを返す */
			return cnt;
		}
	}
	return -1; /* リスト内に値が無かった場合、-1を返す */
}

List_t *list_pickup(List_t *head, int n)
{
	List_t *p;
	int i;

	if(n <= 0 || n > list_length(head)) {
		/* 0以下、リストの要素数より多い数値であった場合
		 * そこには要素が無いのでNULLを返して関数終了 */
		return NULL;
	}
	p = head->next;

	for(i = 1; i < n; ++i) {
		/* n番目まで進める */
		p = p->next;
	}

	return p;
}

List_t list_reverse(List_t *head)
{
	List_t *p, list;
	list.next = NULL; /* リストの最後を示すためのNULLを代入しておく */

	for(p = head->next; p != NULL; p = p->next) {
		/* 1番目の要素を1番目に、2番目の要素を1番目に、3番目の要素を1番目に…
		 * とすることでリストの要素の並びを逆にする */
		insert_first(&list, p->value);
	}

	return list;
}

List_t list_sort(List_t *head)
{
	List_t *p, *q, list;
	int cnt;
	
	list.next = NULL;

	for(p = head->next; p != NULL; p = p->next) {
		/* リスト内の要素を全て辿るためのループ */
		cnt = 1;
		for(q = list.next; q != NULL; q = q->next) {
			/* 昇順にソートされたリストの要素を全て辿るためのループ */
			if(p->value < q->value) {
				/* この条件を満たした場合、そこに要素を挿入するためループを強制的に抜ける */
				break;
			}
			++cnt;
		}
		insert(&list, p->value, cnt);
	}
	return list;
}

List_t list_copy(List_t *head)
{
	List_t *p, list;
	list.next = NULL;

	for(p = head->next; p != NULL; p = p->next) {
		/* 1番目の要素を1番目に、2番目の要素を2番目に…　として同じリストを作成する */
		insert_last(&list, p->value);
	}

	return list;
}